// @algorithm @lc id=516 lang=cpp 
// @title longest-palindromic-subsequence


// #define print(...)
// @test("bbbab")=4
// @test("cbbd")=2
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        const size_t n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
            for(int j=i-1; j>=0; j--){
                if(s[j] == s[i])
                    dp[j][i] = dp[j+1][i-1] + 2;
                else
                    dp[j][i] = max(dp[j+1][i], dp[j][i-1]);
            }
        }
        return dp[0][n-1];
    }
};